package solutions.leetcode.normal

/**
 * @author lizhidong
 * <a href="https://leetcode.cn/problems/count-the-number-of-good-subarrays/">2537. 统计好子数组的数目</a>
 */
private class Solution2537 {
    fun countGood(nums: IntArray, k: Int): Long {
        val cnt = HashMap<Int, Int?>()
        var ans: Long = 0
        var left = 0
        var pairs = 0
        for (x in nums) {
            pairs += cnt.getOrDefault(x, 0) ?: 0
            cnt.merge(x, 1, Integer::sum) // 移入右端点
            while (pairs - (cnt[nums[left]] ?: 1) + 1 >= k) {
                pairs -= (cnt.merge(nums[left++], -1, Integer::sum)) ?: 0; // 移出左端点
            }
            if (pairs >= k) ans += left + 1
        }
        return ans
    }

}

fun main() {
    println(Solution2537().countGood(
        arrayOf(
            3,1,4,3,2,2,4
        ).toIntArray(),
        2
    ))
}